package Binary_tree;

// 从任意节点出发，到任意节点，最大权值累加和
public class Code10_MaxPathSum2 {

    public static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node(int x) {
            val = x;
        }
    }

    public static class Info{
        public int maxPathSum;
        public int fromHeadPathSum;

        public Info(int m, int f){
            maxPathSum = m;
            fromHeadPathSum = f;
        }
    }

    public static Info process(Node x){
        if (x == null){
            return null;
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        // p1,p2与x无关
        int p1 = Integer.MIN_VALUE;
        if (leftInfo != null){
            p1 = leftInfo.maxPathSum;
        }
        int p2 = Integer.MIN_VALUE;
        if (rightInfo != null){
            p2 = rightInfo.maxPathSum;
        }
        // p3,p4,p5与x有关
        int p3 = x.val;
        int p4 = x.val + (leftInfo != null ? leftInfo.fromHeadPathSum : 0);
        int p5 = x.val + (rightInfo != null ? rightInfo.fromHeadPathSum : 0);
        int p6 = Integer.MIN_VALUE;
        if (leftInfo != null && rightInfo != null){
            p6 = leftInfo.fromHeadPathSum + x.val + rightInfo.fromHeadPathSum;
        }

        int maxPathSum = Math.max(Math.max(p1, p2), Math.max(Math.max(p3, p4), Math.max(p5, p6)));
        int fromHeadPathSum = Math.max(p3, Math.max(p4, p5));
        return new Info(maxPathSum, fromHeadPathSum);
    }

    public static void main(String[] args) {
        Node t1 = new Node(1);
        t1.left = new Node(2);
        t1.right = new Node(3);
        t1.left.left = new Node(4);
        t1.left.right = new Node(5);
        t1.right.left = new Node(6);
        t1.right.right = new Node(7);
        System.out.println(process(t1).maxPathSum);
    }
}
